package com.dmall.play.interview.chapter08;

import java.util.LinkedList;
import java.util.Stack;

public class BinarySearchTree<E extends Comparable<E>> {

    static class Node<E> {
        E e;
        Node<E> left, right;

        Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    private int size;
    private Node<E> root;

    public BinarySearchTree() {
        this.size = 0;
        this.root = null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(E e) {
        root = add(root, e);
    }

    private Node<E> add(Node<E> node, E e) {
        if (node == null) {
            size++;
            return new Node<>(e);
        }
        if (node.e.compareTo(e) > 0) {
            node.left = add(node.left, e);
        } else if (node.e.compareTo(e) < 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node<E> node, E e) {
        if (node == null) {
            return false;
        }
        if (node.e.compareTo(e) == 0) {
            return true;
        } else if (node.e.compareTo(e) > 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void preOrderNR() {
        if (root == null) {
            return;
        }
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> cur = stack.pop();
            System.out.println(cur.e);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        preOrder(node.left);
        System.out.println(node.e);
        preOrder(node.right);
    }


    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node<E> node) {
        if (node == null) {
            return;
        }
        preOrder(node.left);
        preOrder(node.right);
        System.out.println(node.e);
    }

    public void levelOrder() {
        if (root == null) {
            return;
        }
        LinkedList<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<E> cur = queue.removeFirst();
            System.out.println(cur.e);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    public E min() {
        if (size == 0) {
            throw new IllegalArgumentException("BinarySearchTree is empty.");
        }
        return min(root).e;
    }

    private Node<E> min(Node<E> node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    public E max() {
        if (size == 0) {
            throw new IllegalArgumentException("BinarySearchTree is empty.");
        }
        return max(root).e;
    }

    private Node<E> max(Node<E> node) {
        if (node.right == null) {
            return node;
        }
        return max(node.right);
    }


    public E removeMin() {
        E min = min();
        root = removeMin(root);
        return min;
    }

    /**
     * 删除掉以node为根的二分搜索树，返回新的根节点
     * @param node 要删除二分搜索树最小值的根节点
     * @return 新的根节点
     */
    private Node<E> removeMin(Node<E> node) {
        if (node.left == null) {
            Node<E> rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax() {
        E max = max();
        root = removeMax(root);
        return max;
    }

    private Node<E> removeMax(Node<E> node) {
        if (node.right == null) {
            Node<E> leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E e) {
        root = remove(root, e);
    }

    private Node<E> remove(Node<E> node, E e) {
        if (node == null) {
            return null;
        }
        if (node.e.compareTo(e) > 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (node.e.compareTo(e) < 0) {
            node.right = remove(node.right, e);
            return node;
        } else {
            // 相等的情况
            if (node.left == null && node.right == null) {
                return null;
            } else if (node.right != null) {
                Node<E> newNode = min(node.right);
                newNode.right = removeMin(node.right);
                newNode.left = node.left;
                node.left = null;
                node.right = null;
                return newNode;
            } else {
                Node<E> newNode = max(node.left);
                newNode.left = removeMax(node.left);
                newNode.right = node.right;
                node.left = null;
                node.right = null;
                return newNode;
            }
        }
    }

    public static void main(String[] args) {
        //////////////////////////
        //          5           //
        //         / \          //
        //        3   6         //
        //       / \   \        //
        //      2   4   8       //
        //////////////////////////
        int[] nums = {5, 3, 6, 8, 4, 2};
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int num : nums) {
            bst.add(num);
        }
        /*bst.preOrder();
        System.out.println("-------------------------------");
        bst.preOrderNR();
        System.out.println("-------------------------------");
        bst.levelOrder();
        System.out.println(bst.contains(2));
        System.out.println(bst.min());
        System.out.println(bst.max());
        System.out.println(bst.removeMin());
        System.out.println(bst.removeMax());*/
        bst.remove(3);
        System.out.println(bst);
    }
}
